import sys
# Install gurobi
!{sys.executable} -m pip install -i https://pypi.gurobi.com gurobipy
!{sys.executable} -m pip install plotly geopy
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import pandas as pd
from itertools import product
import gurobipy as gp
from gurobipy import GRB, quicksum
# These are ours
import problem
import visualization
Looking in indexes: https://pypi.gurobi.com Requirement already satisfied: gurobipy in /opt/anaconda3/lib/python3.8/site-packages (9.1.1) Requirement already satisfied: plotly in /opt/anaconda3/lib/python3.8/site-packages (4.14.3) Requirement already satisfied: geopy in /opt/anaconda3/lib/python3.8/site-packages (2.1.0) Requirement already satisfied: retrying>=1.3.3 in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.3.3) Requirement already satisfied: six in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.15.0) Requirement already satisfied: geographiclib<2,>=1.49 in /opt/anaconda3/lib/python3.8/site-packages (from geopy) (1.50)
def normalize(i, j):
assert i != j
return (i, j) if i < j else (j, i)
from model import Autonomax, Config
# Run on the first |C| cities (mostly for testing)
C = 41
# What scenario we will be utilizing
scenario = 0
# The number of cities in the core net
NC = 4
# 1 if the core net should be a cycle; 0 if it shoul be a path.
Z = 0
autonomax = Autonomax(
Config(
cities=problem.cities[:C],
distances=problem.D[:C, :C],
demand=problem.B[scenario][:C],
core_city_count=NC,
core_net_is_cycle=Z,
)
)
Academic license - for non-commercial use only - expires 2021-05-15 Using license file /Users/sjurwold/gurobi.lic
A = autonomax.model.getA()
count = lambda d: len(d) if isinstance(d, gp.tupledict) else 1
V = sum(count(v) for v in autonomax.variables.values())
C = sum(count(c) for c in autonomax.constraints.values())
print(f'V = {V}, C = {C}')
fig, ax = plt.subplots(1, figsize=(128, 128 * C/V))
ax.set_xticklabels([])
ax.set_yticklabels([])
plt.spy(A)
total = 0
print(f'\nCONSTRAINT SETS:')
for (name, constraint) in autonomax.constraints.items():
constraints_in_set = count(constraint)
print(f'{constraints_in_set:>5} | {name}')
#plt.gcf().text(0.07, 0.69 - 0.4 * (total + 0.5 * count(constraint)) / C, name, fontsize=14)
total += constraints_in_set
plt.plot([0, V], [total - 0.5, total - 0.5], color='grey')
total = 0
print(f'\nVARIABLE SETS:')
for (name, variables) in autonomax.variables.items():
variables_in_set = count(variables)
print(f'{variables_in_set:>5} | {name}')
#plt.gcf().text(0.1 + 0.8 * (total + 0.5*count(variables)) / V, 0.8, name, fontsize=14)
total += count(variables)
plt.plot([total - 0.5, total - 0.5], [0, C], color='grey')
plt.savefig('constraint-matrix.png', dpi=200)
V = 9389, C = 6153
CONSTRAINT SETS:
1 | one_control_center
41 | control_city_directly_connected
1681 | reduce_control_center_symmetry
41 | core_city_ub
1 | cycle_or_path
41 | disallow_core_tree
1 | exactly_nc_core_cities
41 | control_center_is_connected
2460 | is_connectable
123 | is_connected_timestep
41 | connected_graph
41 | conservation_of_flow
820 | force_edge_if_flow
820 | edge_cost_lb
VARIABLE SETS:
41 | is_control_center
820 | is_core_edge
41 | is_core_city
164 | is_connected_step
5043 | is_connectable_step
820 | flow
820 | abs_flow
820 | is_sub_edge
820 | edge_cost
autonomax.model.Params.timeLimit = 600.0
autonomax.model.optimize()
Changed value of parameter timeLimit to 600.0
Prev: inf Min: 0.0 Max: inf Default: inf
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (mac64)
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 6153 rows, 9389 columns and 30299 nonzeros
Model fingerprint: 0x620c19f9
Model has 820 general constraints
Variable types: 2460 continuous, 6929 integer (6929 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+05]
Objective range [1e+00, 2e+04]
Bounds range [1e+00, 1e+02]
RHS range [7e-01, 4e+01]
Presolve removed 93 rows and 2633 columns
Presolve time: 0.09s
Presolved: 6060 rows, 6756 columns, 30309 nonzeros
Variable types: 2460 continuous, 4296 integer (4296 binary)
Found heuristic solution: objective 84902.481928
Root relaxation: objective 1.063333e+03, 5492 iterations, 0.13 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1063.33250 0 184 84902.4819 1063.33250 98.7% - 0s
H 0 0 28631.686435 2393.79536 91.6% - 0s
0 0 2393.79536 0 257 28631.6864 2393.79536 91.6% - 0s
0 0 2520.28857 0 269 28631.6864 2520.28857 91.2% - 0s
0 0 2520.28857 0 269 28631.6864 2520.28857 91.2% - 0s
0 0 2780.84720 0 254 28631.6864 2780.84720 90.3% - 0s
0 0 2780.84720 0 213 28631.6864 2780.84720 90.3% - 1s
H 0 0 19492.252419 2780.84720 85.7% - 1s
0 2 2780.84720 0 207 19492.2524 2780.84720 85.7% - 1s
H 35 38 19411.617554 2780.84720 85.7% 481 2s
H 76 83 17295.249235 2780.84720 83.9% 251 2s
H 77 83 15614.862409 2780.84720 82.2% 248 2s
H 115 112 15582.290546 2780.84720 82.2% 190 2s
H 117 112 15569.777327 2780.84720 82.1% 188 2s
H 122 112 15462.774083 2780.84720 82.0% 183 2s
H 687 632 15356.400285 2780.84720 81.9% 105 5s
H 688 632 15318.120046 2780.84720 81.8% 105 5s
H 694 632 15277.960562 2780.84720 81.8% 105 5s
H 737 676 14907.429344 2780.84720 81.3% 104 5s
H 740 672 14813.759399 2780.84720 81.2% 104 5s
H 741 663 14668.480296 2780.84720 81.0% 104 5s
H 1320 1209 14633.515764 2780.84720 81.0% 96.9 6s
H 1495 1333 14621.890697 2780.84720 81.0% 98.3 7s
1500 1337 8342.16063 47 253 14621.8907 2780.84720 81.0% 98.0 10s
1508 1347 2780.84720 14 243 14621.8907 2780.84720 81.0% 109 15s
H 1580 1303 14576.559761 2851.56500 80.4% 122 19s
1582 1310 9826.39889 20 314 14576.5598 2851.56500 80.4% 123 20s
H 1614 1262 14564.917353 2887.15121 80.2% 127 21s
H 1615 1200 14423.931717 2887.15121 80.0% 127 21s
H 1675 1157 14398.780590 3056.98068 78.8% 130 23s
H 1682 1101 14398.274528 3082.34056 78.6% 130 23s
H 1713 1072 13993.418491 3087.42366 77.9% 132 24s
1778 1084 3115.30718 27 270 13993.4185 3115.30718 77.7% 133 25s
H 1798 1027 13950.457402 3116.36909 77.7% 134 25s
2344 1112 4140.88402 39 222 13950.4574 3209.54117 77.0% 137 30s
3036 1380 5543.08580 57 148 13950.4574 3209.54117 77.0% 135 35s
4047 1691 8613.18608 64 111 13950.4574 3353.41248 76.0% 135 40s
H 5083 2474 13886.992252 4145.20532 70.2% 130 44s
5174 2499 7451.17708 58 119 13886.9923 4145.20532 70.2% 129 45s
H 5242 2675 13799.296440 4193.02558 69.6% 128 46s
6035 3148 cutoff 23 13799.2964 4332.20289 68.6% 130 50s
6981 3524 9715.80260 36 162 13799.2964 4518.48589 67.3% 133 55s
7849 4110 11336.3171 34 138 13799.2964 4644.50648 66.3% 134 60s
H 7873 4110 13799.296438 4644.50648 66.3% 134 60s
H 8256 4229 13799.296422 4703.86453 65.9% 133 61s
9253 4905 6463.13267 22 276 13799.2964 4845.05202 64.9% 130 65s
H 9264 4905 13799.296368 4845.05202 64.9% 130 65s
H 9854 5310 13799.296350 5009.61261 63.7% 132 67s
H10044 5310 13799.296331 5031.95305 63.5% 132 67s
H10271 5310 13799.296329 5064.22110 63.3% 132 67s
H10650 5591 13799.296316 5141.69220 62.7% 133 71s
H10747 5591 13799.296289 5141.69220 62.7% 133 71s
H11005 5774 13799.296271 5141.69220 62.7% 134 73s
11817 6313 6447.85504 46 249 13799.2963 5387.01793 61.0% 134 76s
12755 6539 cutoff 22 13799.2963 5597.99805 59.4% 134 80s
H13018 6768 13799.296106 5674.82574 58.9% 135 82s
13949 7339 9037.92367 56 97 13799.2961 5794.34937 58.0% 135 86s
15433 7941 10227.7781 46 170 13799.2961 6075.99880 56.0% 134 91s
15622 8233 12262.8795 68 85 13799.2961 6121.75103 55.6% 134 97s
16126 8558 9423.16593 54 181 13799.2961 6229.98854 54.9% 134 100s
H16455 8558 13799.296087 6243.99721 54.8% 134 100s
17223 9266 11483.5706 45 147 13799.2961 6342.25312 54.0% 134 105s
H17342 9212 13627.031901 6342.25312 53.5% 133 105s
H18607 9441 13378.777498 6490.04688 51.5% 132 108s
18771 9716 7754.47021 51 180 13378.7775 6523.74384 51.2% 132 111s
19979 10447 12246.9337 44 146 13378.7775 6672.79292 50.1% 133 117s
20991 10690 cutoff 36 13378.7775 6868.10445 48.7% 132 120s
22800 11375 7801.64506 33 259 13378.7775 7057.68130 47.2% 133 125s
24759 11973 8276.95244 70 82 13378.7775 7316.07080 45.3% 134 131s
26399 12296 10570.8011 29 194 13378.7775 7548.60818 43.6% 134 136s
27998 12501 13179.4243 38 154 13378.7775 7861.57061 41.2% 136 142s
28308 12935 12485.4717 61 111 13378.7775 7916.69948 40.8% 136 145s
29323 13291 10049.7194 38 244 13378.7775 8021.66004 40.0% 136 186s
H30037 13291 13378.777410 8050.98600 39.8% 136 186s
30774 13478 10928.0072 45 216 13378.7774 8228.60537 38.5% 138 212s
31133 13606 11356.4753 87 120 13378.7774 8281.72350 38.1% 140 215s
32031 13773 cutoff 36 13378.7774 8382.80360 37.3% 144 223s
H32249 13773 13378.777365 8385.83573 37.3% 145 223s
32664 13827 13357.7506 43 205 13378.7774 8453.04176 36.8% 146 227s
33330 13886 cutoff 71 13378.7774 8490.39284 36.5% 149 232s
H33334 13886 13378.777344 8490.39284 36.5% 149 232s
33878 14002 9161.55255 44 230 13378.7773 8593.04176 35.8% 152 237s
34405 14130 13190.2708 31 379 13378.7773 8645.63227 35.4% 155 242s
35061 14269 cutoff 54 13378.7773 8689.82248 35.0% 157 248s
35762 14340 13258.1183 52 279 13378.7773 8768.18662 34.5% 160 253s
36015 14434 12320.8916 48 120 13378.7773 8772.78893 34.4% 160 259s
36645 14674 13236.0394 54 178 13378.7773 8856.75189 33.8% 163 264s
37325 14730 10143.8589 69 261 13378.7773 8881.03435 33.6% 166 270s
37804 14835 13137.9610 43 241 13378.7773 8935.68867 33.2% 169 275s
38435 15094 12361.9921 35 176 13378.7773 8950.94495 33.1% 171 281s
39328 15237 cutoff 49 13378.7773 9039.22929 32.4% 173 288s
39926 15238 cutoff 91 13378.7773 9080.48068 32.1% 175 294s
40556 15391 10914.6259 91 226 13378.7773 9099.32872 32.0% 177 300s
41376 15639 9816.14609 44 250 13378.7773 9158.13054 31.5% 179 306s
42252 15728 11467.9326 81 136 13378.7773 9248.01404 30.9% 181 334s
42705 15813 cutoff 82 13378.7773 9259.92798 30.8% 182 340s
43446 15853 11477.9641 29 305 13378.7773 9332.51189 30.2% 185 346s
43873 16010 10627.1030 68 209 13378.7773 9358.53918 30.0% 187 351s
44442 16102 cutoff 47 13378.7773 9414.80638 29.6% 188 357s
45132 16211 11222.8843 80 145 13378.7773 9447.73548 29.4% 191 364s
45770 16272 10079.9662 44 159 13378.7773 9485.73154 29.1% 193 371s
46711 16334 10763.8061 76 180 13378.7773 9518.53993 28.9% 195 381s
47077 16488 12304.6531 63 159 13378.7773 9546.05397 28.6% 196 392s
48118 16550 cutoff 63 13378.7773 9593.81374 28.3% 198 399s
48892 16722 11366.1111 117 157 13378.7773 9627.70035 28.0% 201 405s
49844 16810 cutoff 63 13378.7773 9704.97579 27.5% 203 412s
50692 16943 10387.9477 70 218 13378.7773 9728.16626 27.3% 205 418s
51444 16998 cutoff 75 13378.7773 9782.19316 26.9% 207 766s
Cutting planes:
Gomory: 83
Cover: 315
Implied bound: 42
MIR: 232
StrongCG: 4
Flow cover: 607
Inf proof: 35
Zero half: 14
RLT: 311
Relax-and-lift: 44
Explored 51869 nodes (10757862 simplex iterations) in 766.35 seconds
Thread count was 8 (of 8 available processors)
Solution count 10: 13378.8 13378.8 13627 ... 14398.8
Time limit reached
Best objective 1.337877734422e+04, best bound 9.787365231096e+03, gap 26.8441%
city_info = pd.DataFrame(autonomax.city_info())
city_info
| Index | Name | IsCoreCity | IsControlCenter | Demand | IngoingFlow | OutgoingFlow | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | Boden | False | False | 4.5 | 4.000000e+00 | 8.500000e+00 |
| 1 | 1 | Borås | False | False | 0.7 | 1.030000e+01 | 1.100000e+01 |
| 2 | 2 | Eskilstuna | False | False | 1.1 | 1.421085e-13 | 1.099999e+00 |
| 3 | 3 | Falun | False | False | 2.3 | 1.278977e-13 | 2.300000e+00 |
| 4 | 4 | Gävle | False | False | 1.0 | 8.900000e+00 | 9.900000e+00 |
| 5 | 5 | Göteborg | False | False | 5.8 | 3.481659e-13 | 5.800000e+00 |
| 6 | 6 | Halmstad | False | False | 3.4 | 6.100000e+00 | 9.500000e+00 |
| 7 | 7 | Haparanda | False | False | 4.6 | 0.000000e+00 | 4.600000e+00 |
| 8 | 8 | Helsingborg | False | False | 2.2 | 3.900000e+00 | 6.100000e+00 |
| 9 | 9 | Hudiksvall | True | False | 3.9 | 2.740000e+01 | 3.130000e+01 |
| 10 | 10 | Jönköping | False | False | 1.2 | 1.300000e+01 | 1.420000e+01 |
| 11 | 11 | Kalmar | False | False | 4.0 | 1.016076e-12 | 4.000000e+00 |
| 12 | 12 | Karlskrona | False | False | 1.6 | 5.684342e-13 | 1.600000e+00 |
| 13 | 13 | Karlstad | False | False | 0.9 | 1.222134e-12 | 9.000008e-01 |
| 14 | 14 | Kiruna | False | False | 4.0 | 1.278977e-13 | 4.000000e+00 |
| 15 | 15 | Kristianstad | False | False | 3.0 | 5.471179e-13 | 3.000000e+00 |
| 16 | 16 | Lidköping | False | False | 1.2 | 1.340000e+01 | 1.460000e+01 |
| 17 | 17 | Linköping | False | False | 4.1 | 1.800000e+00 | 5.900000e+00 |
| 18 | 18 | Luleå | False | False | 2.0 | 1.310000e+01 | 1.510000e+01 |
| 19 | 19 | Malmö | False | False | 2.6 | 1.300000e+00 | 3.900000e+00 |
| 20 | 20 | Motala | False | False | 2.4 | 5.900000e+00 | 8.300000e+00 |
| 21 | 21 | Norrköping | False | False | 1.7 | 1.705303e-12 | 1.700000e+00 |
| 22 | 22 | Nyköping | False | False | 4.6 | 2.110312e-12 | 4.600000e+00 |
| 23 | 23 | Sandviken | True | False | 4.5 | 4.350000e+01 | 4.800000e+01 |
| 24 | 24 | Skellefteå | False | False | 4.4 | 1.510000e+01 | 1.950000e+01 |
| 25 | 25 | Skövde | True | False | 2.5 | 3.980000e+01 | 4.230000e+01 |
| 26 | 26 | Stockholm | False | False | 7.0 | 1.239897e-12 | 7.000000e+00 |
| 27 | 27 | Sundsvall | False | False | 0.7 | 2.670000e+01 | 2.740000e+01 |
| 28 | 28 | Trelleborg | False | False | 1.3 | 1.548983e-12 | 1.300000e+00 |
| 29 | 29 | Uddevalla | False | False | 4.0 | 5.800000e+00 | 9.800000e+00 |
| 30 | 30 | Umeå | False | False | 3.2 | 1.950000e+01 | 2.270000e+01 |
| 31 | 31 | Uppsala | False | False | 1.9 | 7.000000e+00 | 8.900000e+00 |
| 32 | 32 | Varberg | True | True | 0.8 | 9.500000e+00 | 1.030000e+01 |
| 33 | 33 | Vetlanda | False | False | 2.1 | 1.090000e+01 | 1.300000e+01 |
| 34 | 34 | Vänersborg | False | False | 3.6 | 9.800000e+00 | 1.340000e+01 |
| 35 | 35 | Västervik | False | False | 1.8 | 2.891909e-12 | 1.800000e+00 |
| 36 | 36 | Västerås | False | False | 1.4 | 2.373213e-12 | 1.400000e+00 |
| 37 | 37 | Växjö | False | False | 2.3 | 4.600000e+00 | 6.900000e+00 |
| 38 | 38 | Örebro | True | True | 4.1 | 1.083000e+02 | 1.030287e-13 |
| 39 | 39 | Örnsköldsvik | False | False | 3.1 | 2.270000e+01 | 2.580000e+01 |
| 40 | 40 | Östersund | False | False | 0.9 | 8.100187e-13 | 9.000000e-01 |
edge_info = pd.DataFrame(autonomax.edge_info())
edge_info
| From | To | Type | Flow | Cost | Distance | |
|---|---|---|---|---|---|---|
| 0 | Skellefteå | Umeå | SUB | 19.500000 | 731.139160 | 111 |
| 1 | Skövde | Örebro | CORE | 42.299999 | 1319.999985 | 132 |
| 2 | Karlskrona | Växjö | SUB | 1.600000 | 62.121900 | 102 |
| 3 | Motala | Örebro | SUB | 8.300000 | 241.611348 | 92 |
| 4 | Boden | Kiruna | SUB | -4.000000 | 637.913000 | 291 |
| 5 | Nyköping | Örebro | SUB | 4.600000 | 228.104575 | 131 |
| 6 | Hudiksvall | Sandviken | CORE | 31.300000 | 1319.999985 | 132 |
| 7 | Sundsvall | Östersund | SUB | -0.900000 | 70.870188 | 166 |
| 8 | Halmstad | Helsingborg | SUB | -6.100000 | 145.447337 | 79 |
| 9 | Jönköping | Vetlanda | SUB | -13.000000 | 225.433574 | 65 |
| 10 | Umeå | Örnsköldsvik | SUB | 22.700000 | 849.479945 | 111 |
| 11 | Boden | Luleå | SUB | 8.500000 | 58.656839 | 32 |
| 12 | Lidköping | Skövde | SUB | 14.600000 | 168.360541 | 49 |
| 13 | Eskilstuna | Örebro | SUB | 1.099999 | 36.303256 | 83 |
| 14 | Karlstad | Örebro | SUB | 0.900001 | 29.229986 | 77 |
| 15 | Halmstad | Varberg | SUB | 9.500000 | 167.432227 | 65 |
| 16 | Lidköping | Vänersborg | SUB | -13.400000 | 206.938975 | 60 |
| 17 | Uddevalla | Vänersborg | SUB | 9.800000 | 39.823253 | 21 |
| 18 | Gävle | Sandviken | SUB | 9.900000 | 49.133186 | 25 |
| 19 | Linköping | Motala | SUB | 5.900000 | 77.952787 | 51 |
| 20 | Linköping | Västervik | SUB | -1.800000 | 64.378861 | 97 |
| 21 | Sundsvall | Örnsköldsvik | SUB | -25.800000 | 1177.683887 | 127 |
| 22 | Vetlanda | Växjö | SUB | -6.900000 | 143.305429 | 72 |
| 23 | Borås | Varberg | SUB | -10.299998 | 260.758745 | 84 |
| 24 | Haparanda | Luleå | SUB | 4.600000 | 210.858567 | 124 |
| 25 | Luleå | Skellefteå | SUB | 15.100000 | 742.410242 | 133 |
| 26 | Stockholm | Uppsala | SUB | 7.000000 | 136.873721 | 69 |
| 27 | Kristianstad | Växjö | SUB | 3.000000 | 134.707658 | 120 |
| 28 | Falun | Sandviken | SUB | 2.300000 | 48.115171 | 65 |
| 29 | Norrköping | Örebro | SUB | 1.700000 | 72.868542 | 111 |
| 30 | Gävle | Uppsala | SUB | -8.900000 | 140.802752 | 60 |
| 31 | Sandviken | Örebro | CORE | 48.000000 | 1789.999980 | 179 |
| 32 | Helsingborg | Malmö | SUB | -3.900000 | 67.318060 | 60 |
| 33 | Göteborg | Uddevalla | SUB | 5.800000 | 117.417503 | 70 |
| 34 | Malmö | Trelleborg | SUB | -1.300000 | 18.150077 | 34 |
| 35 | Jönköping | Skövde | SUB | 14.200000 | 337.352659 | 81 |
| 36 | Hudiksvall | Sundsvall | SUB | -27.400000 | 641.652304 | 81 |
| 37 | Västerås | Örebro | SUB | 1.400000 | 49.705664 | 93 |
| 38 | Borås | Skövde | SUB | 10.999998 | 384.262722 | 105 |
| 39 | Kalmar | Vetlanda | SUB | 4.000000 | 174.202753 | 119 |
core_cost = sum(edge_info[edge_info['Type'] == 'CORE']['Cost'])
subnet_cost = sum(edge_info[edge_info['Type'] == 'SUB']['Cost'])
total_cost = core_cost + subnet_cost
print(f'core = {core_cost:>9.3f}')
print(f'subnet = {subnet_cost:>9.3f}')
print('------------------')
print(f'total = {total_cost:>9.3f}')
assert abs(autonomax.model.getObjective().getValue() - total_cost) < 1e-6
core = 4430.000 subnet = 8948.777 ------------------ total = 13378.777
visualization.show(pd.DataFrame(autonomax.city_info()), pd.DataFrame(autonomax.edge_info()))